package org.apache.commons.graph.view.iterator

import com.gitee.wsl.collections.deque.ArrayDeque
import com.gitee.wsl.func.consumer.Consumer
import org.apache.commons.graph.visitor.ITargetVertexVisitor


/**
 * Iterates over the vertices in a directed graph in breadth-first order.
 *
 * @param <V> Vertex type
</V> */
class GraphBreadthFirstIterator<V>(
    private val graph: ITargetVertexVisitor<V>, 
    root: V
) : Iterator<V> {
    private val deque = ArrayDeque<V>()
    private val set = HashSet<V>()

    init {
        this.deque.add(root)
    }

    override fun hasNext(): Boolean {
        return !deque.isEmpty()
    }

    override fun next(): V {
        if (!hasNext()) throw NoSuchElementException()
        return next(deque, graph, set)
    }

    companion object {
        // tell cpd to start ignoring code - CPD-OFF
        /**
         * Populates a set with the nodes reachable from a given node.
         */
        fun <V> reachable(set: MutableSet<V>, graph: ITargetVertexVisitor<V>, root: V) {
            val deque = ArrayDeque<V>()
            deque.add(root)
            set.add(root)
            while (!deque.isEmpty()) {
                next(deque, graph, set)
            }
        }

        // resume CPD analysis - CPD-ON
        private fun <V> next(deque: ArrayDeque<V>, graph: ITargetVertexVisitor<V>, set: MutableSet<V>): V {
            val v = deque.removeFirst()

            graph.forEachTarget(v, Consumer { target: V ->
                if (set.add(target)) {
                    deque.addLast(target)
                }
            })
            return v
        }
    }
}